package jianzhi

func levelOrder3(root *TreeNode) [][]int {
	res := [][]int{}

	if root == nil {
		return res
	}

	stack := []*TreeNode{root}
	level := 0

	for len(stack) > 0 {
		levelLen := len(stack)
		levelRes := []int{}
		for i := 0; i < levelLen; i++ {
			temp := stack[0]
			if temp.Left != nil {
				stack = append(stack, temp.Left)
			}
			if temp.Right != nil {
				stack = append(stack, temp.Right)
			}
			levelRes = append(levelRes, temp.Val)
			stack = stack[1:]
		}

		if level%2 == 1 {
			var mid int = len(levelRes) / 2
			for i := 0; i < mid; i++ {
				levelRes[i], levelRes[len(levelRes)-i-1] = levelRes[len(levelRes)-i-1], levelRes[i]
			}
		}
		level++
		res = append(res, levelRes)
	}

	return res
}
